package array;

/**
 * 4.已知有个升序的数组，要求插入一个元素，该数组顺序依然是升序，比如：
 * [10, 12,45,90]，添加23后,数组为[10, 12,23,45,90]
 */
public class 扩容数组与二分法 {
    public static void main(String[] args) {
        int[] arr = new int[]{10, 12, 45, 90};
        int[] newArr = new int[arr.length + 1];
        //先给新数组赋值
        for (int i = 0; i < arr.length; i++) {
            newArr[i] = arr[i];
        }
        //要插入的值
        int insert = 23;
        /*
        思路，首先定位要插入的下标，用到二分法
        先发现规律（偶数，插入23)【偶数中间有2个数】
            10, 12, 45, 90
             0, 1,  2,  3  ->长度为4，二分就是 4/2 = 2   ,那么要比较的下标就是 2-1 =1，比较a[1]和a[2]
             要插入的数字和 arr[1],比较，看在哪一边，比如23和a[1]=12比较，比他大就是在右边
             然后a[2]=45，和23比较，发现23正好大于a[1]小于a[2],正好可以插入进来
             这个时候返回来的下标就是2,那么对于扩容后的新数组来说，原来的a[2]往最后的数字都要往后移动一位
             那假设我们要插入的数是50，根据二分法右边长度还有2位，一个比较过了，还有一个直接比就可以了

         假设是二分法的奇数插入
         10, 12, 45, 90,100  ->5/2 = 2,这个时候的下标正好在中间
         0, 1,  2,  3,  4
         如果我要插入92
         先和中间比较 arr[2] = 45，发现92大于45，那么就插入到右边
         右边继续二分
         a[2]到尾部，判断长度，发现是奇数，下标为2 和 4 长度为 3 /2  = 1 （int），直接和中间值比较，也就是
         a[2+1]= a[3] = 90,和中间值比较 ，也就是和90比较，发现92大于90，那么就插入到左边，即插入到右边，
         看右边的长度，发现只剩下2个了，直接和最右边的比较即可，也就是92和100比较
         发现92小就插入左边否则插入右边
         返回要插入的下标，也就是92大于的那个下标+1,92小于的那个下标本身，也就是原来对应100的下标
         */
        int len = arr.length;
        int mid = len / 2;
        //如果是偶数
        if(len % 2 == 0){
            if(insert>arr[mid]){
                //在右边
                //也是要判断长度是奇数还是偶数
            }else if(insert<arr[mid-1]){
                //在左边
            }else{
                //在中间，要插入的下标为mid--》2
                System.out.println("要插入的下标:"+mid);
            }
        }else{
            //是奇数
            if(insert>arr[mid]){
                //在右边
            }else if(insert<arr[mid]){
                //在左边
            }else{
                //在中间（正好等于），要插入的下标为mid--》2
                System.out.println("要插入的下标:"+mid+1);
            }

        }





    }

}
